package main

func minPathSum2(grid [][]int) int {
	dp := make([][]int, len(grid))

	min := func(a, b int) int {
		if a > b {
			return b
		}

		return a
	}

	for i := 0; i < len(grid); i++ {
		dp[i] = make([]int, len(grid[0]))
	}

	dp[0][0] = grid[0][0]
	for i := 1; i < len(dp[0]); i++ {
		dp[0][i] += dp[0][i-1] + grid[0][i]
	}

	for i := 1; i < len(dp); i++ {
		dp[i][0] += dp[i-1][0] + grid[i][0]
	}

	for i := 1; i < len(dp); i++ {
		for j := 1; j < len(dp[0]); j++ {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
		}
	}

	return dp[len(dp)-1][len(dp[0])-1]
}

func minPathSum(grid [][]int) int {
	dp := make([]int, len(grid[0]))
	min := func(a, b int) int {
		if a > b {
			return b
		}

		return a
	}
	for i := 0; i < len(dp); i++ {
		if i == 0 {
			dp[i] += grid[0][i]
			continue
		}

		dp[i] = dp[i-1] + grid[0][i]
	}

	for i := 1; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if j == 0 {
				dp[j] = dp[j] + grid[i][j]
				continue
			}

			dp[j] = min(dp[j-1], dp[j]) + grid[i][j]
		}
	}

	return dp[len(dp)-1]
}

func main() {
	minPathSum([][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}})
}
